#ifndef CONJUNTO_HPP_
#define CONJUNTO_HPP_

#include <iostream>
#include "Conj.h"

using namespace std;
using namespace aed2;

class Trie
{

	public:

		// Constructor. Genera un trie vacío.
		Trie();

		// Destructor. Debe dejar limpia la memoria.
		~Trie();

		// Agrega tema a un conjunto de autores
		void agregarTema(const string,  const Conj<string>&);

		// Agrega el autor al Trie
		void agregarAutor(const string);

		const Conj<string>& FTS(const string, Conj<string> &);

		bool estaDefinido(const string);

		//{Se corresponde a la función obtener del TAD, es decir obtiene el significado de una clave.}
		//{Precondición: está definido en el trie}

		Conj<string>& obtenerClave(const string) const;  //{estaDefinido?(t,s)}

		void definirClave(const string, bool);

	private:

		// la representación de un nodo interno.
		struct Nodo
		{
			bool esClave;
			Conj<string> *conjunto;
			// el elemento representa el nodo es de 256 elementos.
			Nodo *array[256];
			// el constructor que representa el nodo.
			Nodo() {

				conjunto = NULL;
				esClave = false;

				for(int i = 0; i < 256; i++)
					array[i] = NULL;
			}

		};

		// Agrega una clave en el trie

		void devolverTodo(Nodo*, Conj<string>&);


		void DestructorAuxiliar(Nodo*);

		//puntero a la raíz del trie.
		Nodo* raiz;

};



Trie::Trie():raiz(NULL){}

Trie::~Trie() {

	DestructorAuxiliar(raiz);

}

void Trie::DestructorAuxiliar(Nodo* p){

    if(p != NULL){
        for(int i = 0; i < 255; i++){
            DestructorAuxiliar(p->array[i]);
        }
        if(p->esClave){
            delete p->conjunto;
        }
        delete p;

    }
}

void Trie::definirClave(const string clave, bool esAutor){
        if (raiz == NULL){
            raiz = new Nodo();
        }
		Nodo* auxiliar = raiz;
        for (int i = 0; i < clave.size(); i++){
            if(auxiliar->array[(int)(clave[i])] == NULL){
                auxiliar->array[(int)(clave[i])] = new Nodo();
            }
            auxiliar = auxiliar->array[(int)(clave[i])];
		}

        auxiliar->esClave = true;
		Conj<string>* c = new Conj<string>;
		if(esAutor){
			auxiliar-> conjunto = c;   //debería apuntar a un conjunto vacío
		}
		else
		{
			c->AgregarRapido(clave);  //debería apuntar a un conjunto que autocontenga el tema
			auxiliar->conjunto = c;

		}

}

Conj<string>& Trie::obtenerClave(const string clave) const{

	Nodo* auxiliar = raiz;
	for(int i = 0; i<clave.size(); i++){
		auxiliar = (auxiliar->array)[(int)(clave[i])];
	}

	return *(auxiliar -> conjunto);
}

void Trie::agregarTema(const string tema, const Conj<string>& c) { //{la referencia es a un conjuto de autores que pertencen al trie}

	Conj<string>::const_Iterador it = c.CrearIt();
	while(it.HaySiguiente()){
		obtenerClave(it.Siguiente()).AgregarRapido(tema);
		it.Avanzar();
	}
	definirClave(tema,false); //¡define el tema en el trie!
}


void Trie::agregarAutor(const string autor){
	definirClave(autor,true);
}

const Conj<string>& Trie::FTS(const string clave, Conj<string> &res) {
	Nodo* auxiliar = raiz;
	int i = 0;
	while(i<clave.size() && clave[i] != '*' && auxiliar != NULL){
		auxiliar = ((auxiliar)->array)[(int)(clave[i])];
		i++;
	}
	if(auxiliar == NULL){
        return res;
    }
    else{
        if(i<clave.size() && clave[i] == '*'){
            devolverTodo(auxiliar,res);
            return res;
        }
        else if(auxiliar->esClave){
            return *(auxiliar->conjunto);
        }
        else{
            return res;
        }
    }
}

template<typename T>
void Union(Conj<T>& c1, const Conj<T>& c2){
    typename Conj<T>::const_Iterador it = c2.CrearIt();

    while(it.HaySiguiente()){

        c1.Agregar(it.Siguiente());
        it.Avanzar();

    }

}

void Trie::devolverTodo(Nodo* auxiliar, Conj<string>& acum) {

	if(auxiliar != NULL){
        if(auxiliar -> esClave){
            Union(acum, *(auxiliar->conjunto));
        }
		for(int i = 0; i < 256; i++){
			devolverTodo((auxiliar->array)[i],acum);
		}
    }
}


bool Trie::estaDefinido(const string clave){

	Nodo* auxiliar = raiz;
	int i = 0;
	while(auxiliar != NULL && i<clave.size()){
		auxiliar = auxiliar->array[(int)(clave[i])];
		i++;
	}

	return (auxiliar != NULL) && (auxiliar->esClave);
}




#endif // CONJUNTO_HPP_
